
/**
 * @constructor
 * @Returns {AStar}
 */
function AStar() {
	
	/**
	 * @private
	 */
	this.area = null;
	
	/**
	 * @private
	 */
	this.distanceCalculator = null;
	
	/**
	 * @private
	 */
	this.exploredNodes = new Array();
	
	/**
	 * @private
	 */
	this.closestNode = null;
};

/**
 * @public
 * @memberOf AStar.prototype
 * @param {number} startX
 * @param {number} startY
 * @param {number} destinationX
 * @param {number} destinationY
 * @param {Area} area
 * @param {DistanceCalculator} distanceCalculator
 * @param {number} somewhatPassableCostMultiplicator 
 * @returns {Path}
 */
AStar.prototype.getPath = function(startX, startY, destinationX, destinationY, area,  distanceCalculator, somewhatPassableCostMultiplicator) {
	var st = new Date().getTime();

	this.reinit(area, distanceCalculator);
	
	var openList = new NodeOpenList(area.getWidth(),area.getHeight());
	var closedList = new NodeList(area.getWidth(),area.getHeight());
	
	var g = distanceCalculator.getDistance(new Node(destinationX,destinationY),new Node(startX,startY));
	var finish = new Node(destinationX,destinationY,g);
	
	var startNode = new Node(startX,startY,0,distanceCalculator.getDistance(new Node(startX,startY),finish));
	
	openList.add(startNode);
	
	var currentNode = null;	
	
	var somewhatPassableGAddendum = UNIT_SIZE*somewhatPassableCostMultiplicator;
	
	var arrivedAtDestination = false;
	while(openList.size!=0) {
		currentNode = openList.getLowestFNode();
		            
        if(finish.equals(currentNode)) {
        	arrivedAtDestination = true;
			break;
		}
        
        openList.remove(currentNode.x,currentNode.y);
        closedList.add(currentNode);
        
        this.processSucessors(currentNode, openList, closedList, finish, area, somewhatPassableGAddendum);
	}
	
	var endNode = null;
	if(arrivedAtDestination) {
		endNode = currentNode;
	} else if(this.closestNode != null) {
		endNode = this.closestNode;
	} else {
		endNode = startNode;
	}
	
	var pathNodesCount = endNode.getParentsCount()+1;
    var pathNodes = new Array();
    var tempNode = endNode;
    var i = 0;
    while(tempNode!=null) {
            pathNodes[pathNodesCount-1-i] = tempNode;
            i = i+1;
            tempNode = tempNode.getParent();
    }

    var computeTimeMs = new Date().getTime() - st;
    return new Path(pathNodes,arrivedAtDestination,computeTimeMs,this.exploredNodes);
};

/**
 * @private
 */
AStar.prototype.processSucessors = function(currentNode, openList, closedList, finish, area, somewhatPassableGAddendum) {
	//Get all neighbors of analyzed node, that DO NOT contain impassable terrain:
	var neighbors = this.distanceCalculator.getNeighbors(currentNode, area);
	
	for(var i = 0; i < neighbors.length; i++) {
		var neighbor = neighbors[i];
		
		//if neighbor node is already IN THE CLOSED LIST, skip it:
        var closedNode = closedList.searchByPosition(neighbor.x, neighbor.y);
        if (closedNode != null) {
        	continue;
        }
				
		//calculate the cost of getting to the neighbor THROUGH the currently analyzed node:
		var newG = currentNode.g + this.distanceCalculator.getDistance(currentNode, neighbor);
		
		//if this neighbor node contains somewhat passable terrain, add some extra value to it's g cost:
		//TODO: this should be made up so that each node can have a specific value for it's extra g cost 
		//(and not simply a constant which applies to all somewhat passable terrain nodes):
		if(area.getTerrainType(neighbor.x, neighbor.y) == TerrainType.SOMEWHAT_PASSABLE) {
			newG = newG+somewhatPassableGAddendum;
		}
		
		//if the neighbor is alerady IN THE OPEN LIST *AND* IT'S THERE WITH A LOWER G COST, skip it
		//as this means that this neighbor is already present in some other path (has some other parent) which is better than
		//what we're investigating rigth now:
		var openNode = openList.searchByPosition(neighbor.x, neighbor.y);
        if (openNode != null && openNode.g <= newG) {
        	continue;
        }

        //if we're here, that means that this neighbor represents a node worth investigating as a potential member of the best path
		
		//if this neighbor is present in the open list, but with a worse (higher) g score, then remove it from the opened list
		//this means that this neighbor has made it to the open list already, but with a parent which constitutes for a path which is
		//longer (costlier) than if it were to go through the currently analysed node (have it as parent)
        if (openNode != null /* implicit: && openNode.g <= newG */) {
            openList.remove(neighbor.x,neighbor.y);
        } else {
        	this.exploredNodes.push(neighbor);
        }
        
		/* 
		 * at this point we know that this neighbor is:
		 * - not on the closed list
		 * - is walkable (does not contain impassable terrain)
		 * - either
		 *    - not on the open list
		 *    - on the open list, but with a g cost higher than if it were to pass through the currently analysed node 
		 *    (aka: if we replace it's current parent with the currently analyzed node, it will make for a less costly (shorter) path
		 * 
		 * Set it's g and h scores, set the currently analyzed node as its parent, and add it to the opened list:		 * 
		 */        
        neighbor.g = newG;
        neighbor.h = this.distanceCalculator.getDistance(neighbor, finish);
        //neighbor.h = 0;
        neighbor.setParent(currentNode);
        
        if(this.closestNode == null || this.closestNode.h > neighbor.h) { 
			this.closestNode = neighbor;
		}
        openList.add(neighbor);        
	}
};

/**
 * @private
 */
AStar.prototype.reinit = function(area,  distanceCalculator) {
	this.area = area;
	this.distanceCalculator = distanceCalculator;
	this.exploredNodes = new Array();
	this.closestNode = null;
};